<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.1.1">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/oldimgs/32.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/oldimgs/16.ico">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.googleapis.com/css?family=sans-serif:300,300italic,400,400italic,700,700italic|Ubuntu:300,300italic,400,400italic,700,700italic|Roboto:300,300italic,400,400italic,700,700italic|'Open+Sans':300,300italic,400,400italic,700,700italic|'Microsoft+YaHei':300,300italic,400,400italic,700,700italic|sans-serif;:300,300italic,400,400italic,700,700italic|Source+Code+Pro:300,300italic,400,400italic,700,700italic|monospace:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">

<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.14.0/css/all.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/pace-js@1.0.2/themes/blue/pace-theme-minimal.css">
  <script src="//cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>

<script class="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"http:/ShuYuMo2003.github.io","root":"/","scheme":"Mist","version":"8.0.0","exturl":false,"sidebar":{"position":"left","width":230,"display":"post","padding":18,"offset":12},"copycode":true,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}};
  </script>

  <meta property="og:type" content="website">
<meta property="og:title" content="Shu Yu Mo&#39;s blog">
<meta property="og:url" content="page/6/index.html">
<meta property="og:site_name" content="Shu Yu Mo&#39;s blog">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="舒雨墨">
<meta property="article:tag" content="Shu Yu Mo&#39;s blog">
<meta property="article:tag" content="Blog">
<meta property="article:tag" content="OI">
<meta property="article:tag" content="Dr_OldSu">
<meta property="article:tag" content="舒阳">
<meta property="article:tag" content="life">
<meta property="article:tag" content="生活">
<meta property="article:tag" content="信息竞赛">
<meta property="article:tag" content="Shu_Yu_Mo">
<meta property="article:tag" content="ShuYuMo">
<meta property="article:tag" content="东营市第一中学">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="page/6/">


<script data-pjax class="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : true,
    isPost : false,
    lang   : 'zh-CN'
  };
</script>

  <title>Shu Yu Mo's blog</title>
  






  <noscript>
  <style>
  body { margin-top: 2rem; }

  .use-motion .menu-item,
  .use-motion .sidebar,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header {
    visibility: visible;
  }

  .use-motion .header,
  .use-motion .site-brand-container .toggle,
  .use-motion .footer { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle,
  .use-motion .custom-logo-image {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line {
    transform: scaleX(1);
  }

  .search-pop-overlay, .sidebar-nav { display: none; }
  .sidebar-panel { display: block; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">Shu Yu Mo's blog</h1>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">远行者</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-links">

    <a href="/link/" rel="section"><i class="fa fa-th fa-fw"></i>links</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
        <li class="menu-item menu-item-templates">

    <a href="/port/" rel="section"><i class="fa fa-heartbeat fa-fw"></i>Templates</a>

  </li>
        <li class="menu-item menu-item-latex">

    <a href="/LaTeX-syntax.html" rel="section"><i class="fa fa-heartbeat fa-fw"></i>LaTeX</a>

  </li>
        <li class="menu-item menu-item-sitemap">

    <a href="/sitemap.xml" rel="section"><i class="fa fa-sitemap fa-fw"></i>站点地图</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-overview-active">
      <ul class="sidebar-nav" style="display:none;">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <section class="post-toc-wrap sidebar-panel">

        <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="舒雨墨"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">舒雨墨</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">106</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">28</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/ShuYuMo2003" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ShuYuMo2003" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.luogu.com.cn/user/44615" title="Luogu → https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;user&#x2F;44615" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>Luogu</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:sujiayi2003@gmail.com" title="E-Mail → mailto:sujiayi2003@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://twitter.com/JiaYiSu5" title="Twitter → https:&#x2F;&#x2F;twitter.com&#x2F;JiaYiSu5" rel="noopener" target="_blank"><i class="fab fa-twitter fa-fw"></i>Twitter</a>
      </span>
  </div>



        <hr/>
      </section>
      <!--/noindex-->

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="舒雨墨"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">舒雨墨</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">106</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">28</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/ShuYuMo2003" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ShuYuMo2003" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.luogu.com.cn/user/44615" title="Luogu → https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;user&#x2F;44615" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>Luogu</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:sujiayi2003@gmail.com" title="E-Mail → mailto:sujiayi2003@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://twitter.com/JiaYiSu5" title="Twitter → https:&#x2F;&#x2F;twitter.com&#x2F;JiaYiSu5" rel="noopener" target="_blank"><i class="fab fa-twitter fa-fw"></i>Twitter</a>
      </span>
  </div>



      </section>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner index posts-expand">
      

      
      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2019/【luogu-2746】【USACO5-3】Network-of-Schools/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/2019/%E3%80%90luogu-2746%E3%80%91%E3%80%90USACO5-3%E3%80%91Network-of-Schools/" class="post-title-link" itemprop="url">【luogu-2746】【USACO5.3】Network of Schools</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2019-08-15 14:49:35" itemprop="dateCreated datePublished" datetime="2019-08-15T14:49:35+08:00">2019-08-15</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2020-04-27 11:33:31" itemprop="dateModified" datetime="2020-04-27T11:33:31+08:00">2020-04-27</time>
      </span>

  
    <span id="2019/【luogu-2746】【USACO5-3】Network-of-Schools/" class="post-meta-item leancloud_visitors" data-flag-title="【luogu-2746】【USACO5.3】Network of Schools" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2019/【luogu-2746】【USACO5-3】Network-of-Schools/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2019/【luogu-2746】【USACO5-3】Network-of-Schools/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>2.3k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>2 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="写在前面"><a href="#写在前面" class="headerlink" title="写在前面"></a>写在前面</h1><p><code>Tarjan</code>缩点经典问题，证明其他题解已经泛滥了。。。我写一写我自己想法。</p>
<h1 id="技巧（KEYS）"><a href="#技巧（KEYS）" class="headerlink" title="技巧（KEYS）"></a>技巧（KEYS）</h1><ul>
<li>任务A：入读为$0$的点的个数</li>
<li>任务B: 求入度为$0$的点数与出度为0的点的个数的最大值值。</li>
</ul>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/2019/【luogu-2746】【USACO5-3】Network-of-Schools/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2019/【luogu-3203】【HNOI2010】弹飞绵羊/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/2019/%E3%80%90luogu-3203%E3%80%91%E3%80%90HNOI2010%E3%80%91%E5%BC%B9%E9%A3%9E%E7%BB%B5%E7%BE%8A/" class="post-title-link" itemprop="url">【luogu-3203】【HNOI2010】弹飞绵羊</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2019-08-15 14:39:12" itemprop="dateCreated datePublished" datetime="2019-08-15T14:39:12+08:00">2019-08-15</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2020-04-27 11:33:31" itemprop="dateModified" datetime="2020-04-27T11:33:31+08:00">2020-04-27</time>
      </span>

  
    <span id="2019/【luogu-3203】【HNOI2010】弹飞绵羊/" class="post-meta-item leancloud_visitors" data-flag-title="【luogu-3203】【HNOI2010】弹飞绵羊" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2019/【luogu-3203】【HNOI2010】弹飞绵羊/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2019/【luogu-3203】【HNOI2010】弹飞绵羊/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>2.2k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>2 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <p>分块，代码思路很明显。</p>
<p>有很多细节，注意分块维护要维护整个区间的信息，不要只修改一个点。</p>
<p>细节死亡……</p>
<pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token comment">/*!
 * FileName: luogu-3203.cpp

&lt;!-- more -->
 * This Problem is on luogu. The ID of the problem is 3203. 
 * Copyright(c) 2019 Shu_Yu_Mo
 * MIT Licensed
 * Luogu: https://www.luogu.org/space/show?uid=44615
 * Github: https://github.com/oldsuold/
 * Gitee: https://gitee.com/Shu_Yu_Mo/
 * These words were created by an amazing tool on 2019-08-14 10:18:06 written by Shu_Yu_Mo.
 */</span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cmath></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cmath></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;vector></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;queue></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;algorithm></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">inf <span class="token number">0x7fffffff</span></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> _ <span class="token operator">=</span> <span class="token number">201000</span><span class="token punctuation">;</span>
<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">char</span> c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">int</span> sign <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">int</span> x <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>c <span class="token operator">></span> <span class="token string">'9'</span> <span class="token operator">||</span> c <span class="token operator">&lt;</span> <span class="token string">'0'</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>c<span class="token operator">==</span><span class="token string">'-'</span><span class="token punctuation">)</span>sign <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> 
    <span class="token keyword">while</span><span class="token punctuation">(</span>c <span class="token operator">&lt;=</span> <span class="token string">'9'</span> <span class="token operator">&amp;&amp;</span> c <span class="token operator">>=</span> <span class="token string">'0'</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> x <span class="token operator">*=</span> <span class="token number">10</span><span class="token punctuation">;</span> x <span class="token operator">+=</span> c <span class="token operator">-</span> <span class="token string">'0'</span><span class="token punctuation">;</span> c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> x <span class="token operator">*</span> sign<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> n<span class="token punctuation">,</span> m<span class="token punctuation">;</span>
<span class="token keyword">int</span> num<span class="token punctuation">;</span>
<span class="token keyword">int</span> belong<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> step<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> NxtNode<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> block<span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">updata</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
	<span class="token keyword">int</span> node <span class="token operator">=</span> x<span class="token punctuation">;</span>
	<span class="token keyword">int</span> sk <span class="token operator">=</span> belong<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> S <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span>belong<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">==</span> sk<span class="token punctuation">)</span>
	<span class="token punctuation">&#123;</span>
		S <span class="token operator">+=</span> step<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">;</span>
		x <span class="token operator">=</span> NxtNode<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	step<span class="token punctuation">[</span>node<span class="token punctuation">]</span> <span class="token operator">=</span> S<span class="token punctuation">;</span> 
	NxtNode<span class="token punctuation">[</span>node<span class="token punctuation">]</span> <span class="token operator">=</span> x<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">query</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
	<span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span>x <span class="token operator">&lt;=</span> n<span class="token punctuation">)</span>
	<span class="token punctuation">&#123;</span>
		ans <span class="token operator">+=</span> step<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">;</span>
		x <span class="token operator">=</span> NxtNode<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> SP<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span> 
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
<span class="token comment">// 	freopen("data.in", "r", stdin);</span>
	n <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>block <span class="token operator">=</span> <span class="token function">sqrt</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
	<span class="token punctuation">&#123;</span>
		<span class="token keyword">int</span> tmp <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		SP<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> tmp<span class="token punctuation">;</span>
		NxtNode<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> tmp <span class="token operator">+</span> i<span class="token punctuation">;</span>
		step<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	num <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
		belong<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span>i <span class="token operator">></span> num <span class="token operator">*</span> block<span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token punctuation">(</span><span class="token operator">++</span> num<span class="token punctuation">)</span> <span class="token operator">:</span> num<span class="token punctuation">;</span>

	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> n<span class="token punctuation">;</span>i <span class="token operator">>=</span> <span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token function">updata</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">//	cout&lt;&lt;"belong: " ; for(register int i = 1;i &lt;= n;i++) printf("%d ", belong[i]) ;cout&lt;&lt;endl;</span>
<span class="token comment">//	for(register int i = 1;i &lt;= n;i++)</span>
<span class="token comment">//	&#123;</span>
<span class="token comment">//		printf(":%d :  ", i);</span>
<span class="token comment">//		printf("step = %d, ", step[i]);</span>
<span class="token comment">//		printf("NxtNode = %d \n", NxtNode[i]);</span>
<span class="token comment">//	&#125;</span>

	m <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span>m <span class="token operator">--</span><span class="token punctuation">)</span>
	<span class="token punctuation">&#123;</span>
		<span class="token keyword">int</span> opt <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>opt <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span>
		<span class="token punctuation">&#123;</span>
			<span class="token keyword">int</span> x <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
			<span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token function">query</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span>
			<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d\n"</span><span class="token punctuation">,</span> ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">&#125;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>opt <span class="token operator">==</span> <span class="token number">2</span><span class="token punctuation">)</span>
		<span class="token punctuation">&#123;</span>
			<span class="token keyword">int</span> x <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
			<span class="token keyword">int</span> val <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
			SP<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">=</span> val<span class="token punctuation">;</span>
			NxtNode<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">=</span> x <span class="token operator">+</span> val<span class="token punctuation">;</span>
			step<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token comment">//			int nowk = belong[x];</span>
			
			<span class="token keyword">int</span> L <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>belong<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">*</span> block<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
			<span class="token keyword">int</span> R <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>belong<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">*</span> block<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">//			printf("Updata %d to %d\n", x, L);</span>
			<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> L<span class="token punctuation">;</span>i <span class="token operator">&lt;=</span> R<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span> step<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">,</span> NxtNode<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> i <span class="token operator">+</span> SP<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
			<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> x<span class="token punctuation">;</span>i <span class="token operator">>=</span> L<span class="token punctuation">;</span>i<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token function">updata</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">//			for(register int i = 1;i &lt;= n;i++)</span>
<span class="token comment">//			&#123;</span>
<span class="token comment">//				printf(":%d :  ", i);</span>
<span class="token comment">//				printf("step = %d, ", step[i]);</span>
<span class="token comment">//				printf("NxtNode = %d \n", NxtNode[i]);</span>
<span class="token comment">//			&#125;</span>
<span class="token comment">//			</span>
		<span class="token punctuation">&#125;</span>
		
	<span class="token punctuation">&#125;</span>
	
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token comment">/*
6
1 2 3 2 5 1
*/</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>


      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2019/【luogu-3469-】【POI2008】BLO-Blockade/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/2019/%E3%80%90luogu-3469-%E3%80%91%E3%80%90POI2008%E3%80%91BLO-Blockade/" class="post-title-link" itemprop="url"> 【luogu-3469 】【POI2008】BLO-Blockade</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2019-08-15 14:07:10" itemprop="dateCreated datePublished" datetime="2019-08-15T14:07:10+08:00">2019-08-15</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2020-04-27 11:34:37" itemprop="dateModified" datetime="2020-04-27T11:34:37+08:00">2020-04-27</time>
      </span>

  
    <span id="2019/【luogu-3469-】【POI2008】BLO-Blockade/" class="post-meta-item leancloud_visitors" data-flag-title=" 【luogu-3469 】【POI2008】BLO-Blockade" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2019/【luogu-3469-】【POI2008】BLO-Blockade/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2019/【luogu-3469-】【POI2008】BLO-Blockade/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>2.4k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>2 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="写在前面"><a href="#写在前面" class="headerlink" title="写在前面"></a>写在前面</h1><p>这是一道剖析算法本质的题目</p>
<h1 id="关于Tarjan"><a href="#关于Tarjan" class="headerlink" title="关于Tarjan"></a>关于<code>Tarjan</code></h1><blockquote>
<p><code>Tarjan</code>的本质就是一个<code>DFS</code><br>                ——苟新杰老师</p>
</blockquote>
<p>既然是<code>DFS</code>，那么在执行的过程中会形成一颗<code>DFS</code>树。</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/2019/【luogu-3469-】【POI2008】BLO-Blockade/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2019/【luogu-2341】【HAOI2006】受欢迎的牛/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/2019/%E3%80%90luogu-2341%E3%80%91%E3%80%90HAOI2006%E3%80%91%E5%8F%97%E6%AC%A2%E8%BF%8E%E7%9A%84%E7%89%9B/" class="post-title-link" itemprop="url"> 【luogu-2341】【HAOI2006】受欢迎的牛</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2019-08-10 23:53:56" itemprop="dateCreated datePublished" datetime="2019-08-10T23:53:56+08:00">2019-08-10</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2020-04-27 11:33:31" itemprop="dateModified" datetime="2020-04-27T11:33:31+08:00">2020-04-27</time>
      </span>

  
    <span id="2019/【luogu-2341】【HAOI2006】受欢迎的牛/" class="post-meta-item leancloud_visitors" data-flag-title=" 【luogu-2341】【HAOI2006】受欢迎的牛" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2019/【luogu-2341】【HAOI2006】受欢迎的牛/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2019/【luogu-2341】【HAOI2006】受欢迎的牛/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>2.8k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>3 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h1><p>每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶</p>
<p>牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜</p>
<p>欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你</p>
<p>算出有多少头奶牛可以当明星。</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/2019/【luogu-2341】【HAOI2006】受欢迎的牛/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2019/【luogu-1993】小K的农场/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/2019/%E3%80%90luogu-1993%E3%80%91%E5%B0%8FK%E7%9A%84%E5%86%9C%E5%9C%BA/" class="post-title-link" itemprop="url">【luogu-1993】小K的农场</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2019-08-06 10:59:52" itemprop="dateCreated datePublished" datetime="2019-08-06T10:59:52+08:00">2019-08-06</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2020-04-27 11:33:31" itemprop="dateModified" datetime="2020-04-27T11:33:31+08:00">2020-04-27</time>
      </span>

  
    <span id="2019/【luogu-1993】小K的农场/" class="post-meta-item leancloud_visitors" data-flag-title="【luogu-1993】小K的农场" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2019/【luogu-1993】小K的农场/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2019/【luogu-1993】小K的农场/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>2.8k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>3 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="差分约束系统"><a href="#差分约束系统" class="headerlink" title="差分约束系统"></a>差分约束系统</h1><p>由$n$个变量$X_1, X_2, X_3 …. X_n$和$m$个未知条件组成的$n$元一次不等式组，</p>
<p>其中，每个条件都形如$X_i \le X_j + W_k$</p>
<p>我们的问题是：如果有解给出一组满足所有条件的解，否则判断出无解</p>
<p>注意到，$X_i \le X_j + W_k$与单源最短路中的三角不等式很相似。</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/2019/【luogu-1993】小K的农场/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2019/【luogu-1967】【NOIP2013】货车运输/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/2019/%E3%80%90luogu-1967%E3%80%91%E3%80%90NOIP2013%E3%80%91%E8%B4%A7%E8%BD%A6%E8%BF%90%E8%BE%93/" class="post-title-link" itemprop="url">【luogu-1967】【NOIP2013】货车运输</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2019-08-04 23:54:34" itemprop="dateCreated datePublished" datetime="2019-08-04T23:54:34+08:00">2019-08-04</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2020-04-27 11:33:31" itemprop="dateModified" datetime="2020-04-27T11:33:31+08:00">2020-04-27</time>
      </span>

  
    <span id="2019/【luogu-1967】【NOIP2013】货车运输/" class="post-meta-item leancloud_visitors" data-flag-title="【luogu-1967】【NOIP2013】货车运输" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2019/【luogu-1967】【NOIP2013】货车运输/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2019/【luogu-1967】【NOIP2013】货车运输/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>2.4k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>2 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <p>首先重新建图，构造出最大生成树，然后在最大生成树上求LCA来回答询问（倍增求树上路径上最小边权）。</p>
<pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cmath></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;algorithm></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;ctime></span></span>

<span class="token operator">&lt;</span><span class="token operator">!</span><span class="token operator">--</span> more <span class="token operator">--</span><span class="token operator">></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">inf <span class="token number">0x7fffffff</span></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">int</span> n<span class="token punctuation">,</span> m<span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> _N <span class="token operator">=</span> <span class="token number">10100</span><span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> _M <span class="token operator">=</span> <span class="token number">100100</span><span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> _Lg <span class="token operator">=</span> <span class="token number">20</span><span class="token punctuation">;</span>
<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
	<span class="token keyword">int</span> x <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> sign <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">char</span> c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span>c <span class="token operator">&lt;</span> <span class="token string">'0'</span> <span class="token operator">||</span> c <span class="token operator">></span> <span class="token string">'9'</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>c <span class="token operator">==</span> <span class="token string">'-'</span><span class="token punctuation">)</span> sign <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span>c <span class="token operator">>=</span> <span class="token string">'0'</span> <span class="token operator">&amp;&amp;</span> c <span class="token operator">&lt;=</span> <span class="token string">'9'</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>x <span class="token operator">=</span> <span class="token punctuation">(</span>x <span class="token operator">&lt;&lt;</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token punctuation">(</span>x <span class="token operator">&lt;&lt;</span> <span class="token number">3</span><span class="token punctuation">)</span><span class="token punctuation">;</span> x <span class="token operator">+=</span> c <span class="token operator">-</span> <span class="token string">'0'</span><span class="token punctuation">;</span>c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
	<span class="token keyword">return</span> x <span class="token operator">*</span> sign<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">struct</span> <span class="token class-name">__edges</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">int</span> u<span class="token punctuation">;</span>
	<span class="token keyword">int</span> v<span class="token punctuation">;</span>
	<span class="token keyword">int</span> w<span class="token punctuation">;</span>
	<span class="token keyword">bool</span> <span class="token keyword">operator</span> <span class="token operator">&lt;</span> <span class="token punctuation">(</span><span class="token keyword">const</span> __edges A<span class="token punctuation">)</span> <span class="token keyword">const</span> <span class="token punctuation">&#123;</span>
		<span class="token keyword">return</span> w <span class="token operator">></span> A<span class="token punctuation">.</span>w<span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>E<span class="token punctuation">[</span>_M<span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">int</span> f<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">init</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>  f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> i<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">find</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">return</span> f<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">==</span> x <span class="token operator">?</span> x <span class="token operator">:</span> f<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">find</span><span class="token punctuation">(</span>f<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token keyword">void</span> <span class="token function">marge</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">,</span> <span class="token keyword">int</span> y<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> x <span class="token operator">=</span> <span class="token function">find</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span> y <span class="token operator">=</span> <span class="token function">find</span><span class="token punctuation">(</span>y<span class="token punctuation">)</span><span class="token punctuation">;</span>f<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">=</span> y<span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
<span class="token keyword">bool</span> <span class="token function">ask</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">,</span> <span class="token keyword">int</span> y<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">return</span> <span class="token function">find</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token function">find</span><span class="token punctuation">(</span>y<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> head<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">struct</span> <span class="token class-name">edges</span><span class="token punctuation">&#123;</span>
	<span class="token keyword">int</span> node<span class="token punctuation">;</span>
	<span class="token keyword">int</span> w<span class="token punctuation">;</span>
	<span class="token keyword">int</span> nxt<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>edge<span class="token punctuation">[</span>_M<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> tot <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> u<span class="token punctuation">,</span> <span class="token keyword">int</span> v<span class="token punctuation">,</span> <span class="token keyword">int</span> w<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
	edge<span class="token punctuation">[</span><span class="token operator">++</span>tot<span class="token punctuation">]</span><span class="token punctuation">.</span>nxt <span class="token operator">=</span> head<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token punctuation">;</span>
	head<span class="token punctuation">[</span>u<span class="token punctuation">]</span> <span class="token operator">=</span> tot<span class="token punctuation">;</span>
	edge<span class="token punctuation">[</span>tot<span class="token punctuation">]</span><span class="token punctuation">.</span>node <span class="token operator">=</span> v<span class="token punctuation">;</span>
	edge<span class="token punctuation">[</span>tot<span class="token punctuation">]</span><span class="token punctuation">.</span>w <span class="token operator">=</span> w<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">void</span> <span class="token function">MakeTree</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i <span class="token operator">&lt;=</span> m<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span><span class="token function">ask</span><span class="token punctuation">(</span>E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>u<span class="token punctuation">,</span> E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token punctuation">)</span><span class="token punctuation">)</span>
		<span class="token punctuation">&#123;</span>
			<span class="token function">add</span><span class="token punctuation">(</span>E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>u<span class="token punctuation">,</span> E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token punctuation">,</span> E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>w<span class="token punctuation">)</span><span class="token punctuation">;</span>
			<span class="token function">add</span><span class="token punctuation">(</span>E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token punctuation">,</span> E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>u<span class="token punctuation">,</span> E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>w<span class="token punctuation">)</span><span class="token punctuation">;</span>
			<span class="token function">marge</span><span class="token punctuation">(</span>E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>u<span class="token punctuation">,</span> E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> anc<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">[</span>_Lg <span class="token operator">+</span> <span class="token number">10</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> Min<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">[</span>_Lg <span class="token operator">+</span> <span class="token number">10</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> dep<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">bool</span> vis<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">dfs</span><span class="token punctuation">(</span><span class="token keyword">int</span> now<span class="token punctuation">,</span> <span class="token keyword">int</span> fa<span class="token punctuation">,</span> <span class="token keyword">int</span> deepth<span class="token punctuation">,</span> <span class="token keyword">int</span> wToFa<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>vis<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>
	vis<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
	dep<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> deepth<span class="token punctuation">;</span>
	anc<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> fa<span class="token punctuation">;</span>
	Min<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> wToFa<span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> head<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">;</span>i<span class="token punctuation">;</span>i <span class="token operator">=</span> edge<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>nxt<span class="token punctuation">)</span>
		<span class="token function">dfs</span><span class="token punctuation">(</span>edge<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>node<span class="token punctuation">,</span> now<span class="token punctuation">,</span> deepth <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> edge<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>w<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> <span class="token function">query</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">,</span> <span class="token keyword">int</span> y<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>dep<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">&lt;</span> dep<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token function">swap</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span> y<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> ans <span class="token operator">=</span> inf<span class="token punctuation">;</span>
	<span class="token keyword">int</span> Dis <span class="token operator">=</span> <span class="token punctuation">(</span>dep<span class="token punctuation">[</span>x<span class="token punctuation">]</span> <span class="token operator">-</span> dep<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>Dis <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">;</span>i <span class="token operator">++</span><span class="token punctuation">,</span> Dis <span class="token operator">>>=</span> <span class="token number">1</span><span class="token punctuation">)</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>Dis <span class="token operator">&amp;</span> <span class="token number">1</span><span class="token punctuation">)</span> ans <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span> Min<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> x <span class="token operator">=</span> anc<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span>x <span class="token operator">==</span> y<span class="token punctuation">)</span> <span class="token keyword">return</span> ans<span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> _Lg<span class="token punctuation">;</span>i <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">--</span><span class="token punctuation">)</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>anc<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">!=</span> anc<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
			ans <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span> <span class="token function">min</span><span class="token punctuation">(</span>Min<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> Min<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">,</span>x <span class="token operator">=</span> anc<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> y <span class="token operator">=</span> anc<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
	ans <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span> <span class="token function">min</span><span class="token punctuation">(</span>Min<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">,</span> Min<span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
	n <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> m <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">init</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i <span class="token operator">&lt;=</span> m<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
	<span class="token punctuation">&#123;</span>
		E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>u <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>v <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		E<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>w <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token function">sort</span><span class="token punctuation">(</span>E <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> E <span class="token operator">+</span> <span class="token number">1</span> <span class="token operator">+</span> m<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">MakeTree</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">memset</span><span class="token punctuation">(</span>vis<span class="token punctuation">,</span> <span class="token boolean">false</span><span class="token punctuation">,</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span>vis<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>vis<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
			<span class="token function">dfs</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span> i<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>j <span class="token operator">&lt;=</span> _Lg<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
			anc<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> anc<span class="token punctuation">[</span>anc<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>j <span class="token operator">&lt;=</span> _Lg<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
			Min<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>Min<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span> Min<span class="token punctuation">[</span>anc<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> Q <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span>Q<span class="token operator">--</span><span class="token punctuation">)</span>
	<span class="token punctuation">&#123;</span>
		<span class="token keyword">int</span> tmpu <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> tmpv <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> ans<span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">ask</span><span class="token punctuation">(</span>tmpu<span class="token punctuation">,</span> tmpv<span class="token punctuation">)</span><span class="token punctuation">)</span>
			ans <span class="token operator">=</span> <span class="token function">query</span><span class="token punctuation">(</span>tmpu<span class="token punctuation">,</span> tmpv<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">else</span>
			ans <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d\n"</span><span class="token punctuation">,</span> ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">&#125;</span>
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2019/【luogu-3398】仓鼠找sugar/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/2019/%E3%80%90luogu-3398%E3%80%91%E4%BB%93%E9%BC%A0%E6%89%BEsugar/" class="post-title-link" itemprop="url">【luogu-3398】仓鼠找sugar</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2019-08-04 23:30:54" itemprop="dateCreated datePublished" datetime="2019-08-04T23:30:54+08:00">2019-08-04</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2020-04-27 11:33:31" itemprop="dateModified" datetime="2020-04-27T11:33:31+08:00">2020-04-27</time>
      </span>

  
    <span id="2019/【luogu-3398】仓鼠找sugar/" class="post-meta-item leancloud_visitors" data-flag-title="【luogu-3398】仓鼠找sugar" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2019/【luogu-3398】仓鼠找sugar/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2019/【luogu-3398】仓鼠找sugar/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>2.4k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>2 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <p>这道题我服了</p>
<h1 id="题意"><a href="#题意" class="headerlink" title="题意"></a>题意</h1><p>询问树上$a$到$b$，$c$到$d$的两条路径是否相交。</p>
<h1 id="做法"><a href="#做法" class="headerlink" title="做法"></a>做法</h1><p>我们容易发现，如果相交，记$x=lca(a,b)$，$y=lca(c,d)$，则必有$x$在$c-d$路径上或$y$在$a-b$路径上。</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/2019/【luogu-3398】仓鼠找sugar/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2019/「YuGu P1352」没有上司的舞会/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/2019/%E3%80%8CYuGu%20P1352%E3%80%8D%E6%B2%A1%E6%9C%89%E4%B8%8A%E5%8F%B8%E7%9A%84%E8%88%9E%E4%BC%9A/" class="post-title-link" itemprop="url">「YuGu P1352」没有上司的舞会</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2019-08-04 11:03:12" itemprop="dateCreated datePublished" datetime="2019-08-04T11:03:12+08:00">2019-08-04</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2021-01-09 21:27:59" itemprop="dateModified" datetime="2021-01-09T21:27:59+08:00">2021-01-09</time>
      </span>

  
    <span id="2019/「YuGu P1352」没有上司的舞会/" class="post-meta-item leancloud_visitors" data-flag-title="「YuGu P1352」没有上司的舞会" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2019/「YuGu P1352」没有上司的舞会/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2019/「YuGu P1352」没有上司的舞会/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>1k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>1 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <p>树形<code>DP</code></p>
<p>存在负点权，无法使用二分图染色</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/2019/「YuGu P1352」没有上司的舞会/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2019/【luogu-3384】【模板】树链剖分/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/2019/%E3%80%90luogu-3384%E3%80%91%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E6%A0%91%E9%93%BE%E5%89%96%E5%88%86/" class="post-title-link" itemprop="url">【luogu-3384】【模板】树链剖分</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2019-08-04 10:01:50" itemprop="dateCreated datePublished" datetime="2019-08-04T10:01:50+08:00">2019-08-04</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2020-04-27 11:33:31" itemprop="dateModified" datetime="2020-04-27T11:33:31+08:00">2020-04-27</time>
      </span>

  
    <span id="2019/【luogu-3384】【模板】树链剖分/" class="post-meta-item leancloud_visitors" data-flag-title="【luogu-3384】【模板】树链剖分" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2019/【luogu-3384】【模板】树链剖分/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2019/【luogu-3384】【模板】树链剖分/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>4k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>4 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cmath></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;algorithm></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;queue></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">inf <span class="token number">0x7fffffff</span></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token operator">&lt;</span><span class="token operator">!</span><span class="token operator">--</span> more <span class="token operator">--</span><span class="token operator">></span>
<span class="token keyword">const</span> <span class="token keyword">int</span> _N <span class="token operator">=</span> <span class="token number">2e5</span> <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> _M <span class="token operator">=</span> <span class="token number">2e5</span> <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> MOD<span class="token punctuation">;</span>
<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> x <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> sign <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">char</span> c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>c <span class="token operator">&lt;</span> <span class="token string">'0'</span> <span class="token operator">||</span> c <span class="token operator">></span> <span class="token string">'9'</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>c <span class="token operator">==</span> <span class="token string">'-'</span><span class="token punctuation">)</span> sign <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>c <span class="token operator">>=</span> <span class="token string">'0'</span> <span class="token operator">&amp;&amp;</span> c <span class="token operator">&lt;=</span> <span class="token string">'9'</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>x <span class="token operator">=</span> <span class="token punctuation">(</span>x <span class="token operator">&lt;&lt;</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token punctuation">(</span>x <span class="token operator">&lt;&lt;</span> <span class="token number">3</span><span class="token punctuation">)</span><span class="token punctuation">;</span> x <span class="token operator">+=</span> c <span class="token operator">-</span> <span class="token string">'0'</span><span class="token punctuation">;</span>c <span class="token operator">=</span> <span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> x <span class="token operator">*</span> sign<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> NodeVal<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">struct</span> <span class="token class-name">edges</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> node<span class="token punctuation">;</span>
    <span class="token keyword">int</span> nxt<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>edge<span class="token punctuation">[</span>_M<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> head<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> tot <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> u<span class="token punctuation">,</span> <span class="token keyword">int</span> v<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    edge<span class="token punctuation">[</span><span class="token operator">++</span>tot<span class="token punctuation">]</span><span class="token punctuation">.</span>nxt <span class="token operator">=</span> head<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token punctuation">;</span>
    head<span class="token punctuation">[</span>u<span class="token punctuation">]</span> <span class="token operator">=</span> tot<span class="token punctuation">;</span>
    edge<span class="token punctuation">[</span>tot<span class="token punctuation">]</span><span class="token punctuation">.</span>node <span class="token operator">=</span> v<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> fa<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> size<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> MaxSon<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> depth<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> _dfsClock <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> top<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> dfn<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> _rank<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">dfsinit</span><span class="token punctuation">(</span><span class="token keyword">int</span> now<span class="token punctuation">,</span> <span class="token keyword">int</span> F<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    fa<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> F<span class="token punctuation">;</span>
    size<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
    MaxSon<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> nowMax <span class="token operator">=</span> <span class="token operator">-</span>inf<span class="token punctuation">;</span>
    depth<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> depth<span class="token punctuation">[</span>F<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> head<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">;</span>i<span class="token punctuation">;</span>i <span class="token operator">=</span> edge<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>nxt<span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> exNode <span class="token operator">=</span> edge<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>node<span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>exNode <span class="token operator">==</span> F<span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
        <span class="token function">dfsinit</span><span class="token punctuation">(</span>exNode<span class="token punctuation">,</span> now<span class="token punctuation">)</span><span class="token punctuation">;</span>
        size<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">+=</span> size<span class="token punctuation">[</span>exNode<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>nowMax <span class="token operator">&lt;</span> size<span class="token punctuation">[</span>exNode<span class="token punctuation">]</span><span class="token punctuation">)</span>
        <span class="token punctuation">&#123;</span>
            nowMax <span class="token operator">=</span> size<span class="token punctuation">[</span>exNode<span class="token punctuation">]</span><span class="token punctuation">;</span>
            MaxSon<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> exNode<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">void</span> <span class="token function">Dfs_Lct</span><span class="token punctuation">(</span><span class="token keyword">int</span> now<span class="token punctuation">,</span> <span class="token keyword">int</span> Top<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    top<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> Top<span class="token punctuation">;</span>
    dfn<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token operator">++</span>_dfsClock<span class="token punctuation">;</span>
    _rank<span class="token punctuation">[</span>_dfsClock<span class="token punctuation">]</span> <span class="token operator">=</span> now<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>MaxSon<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>
    <span class="token function">Dfs_Lct</span><span class="token punctuation">(</span>MaxSon<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">,</span> Top<span class="token punctuation">)</span><span class="token punctuation">;</span>
    
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> head<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">;</span>i<span class="token punctuation">;</span>i <span class="token operator">=</span> edge<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>nxt<span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> exNode <span class="token operator">=</span> edge<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>node<span class="token punctuation">;</span>
        
        <span class="token keyword">if</span><span class="token punctuation">(</span>exNode <span class="token operator">!=</span> MaxSon<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">&amp;&amp;</span> exNode <span class="token operator">!=</span> fa<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">)</span>
         	<span class="token function">Dfs_Lct</span><span class="token punctuation">(</span>exNode<span class="token punctuation">,</span> exNode<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>	
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> Vall<span class="token punctuation">[</span>_N<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">struct</span> <span class="token class-name">Node</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> sum<span class="token punctuation">;</span>
    <span class="token keyword">int</span> tar<span class="token punctuation">;</span>
    Node <span class="token operator">*</span>lson<span class="token punctuation">,</span> <span class="token operator">*</span> rson<span class="token punctuation">;</span>
    <span class="token function">Node</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> sum <span class="token operator">=</span> tar <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>lson <span class="token operator">=</span> rson <span class="token operator">=</span> <span class="token constant">NULL</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
    <span class="token function">Node</span><span class="token punctuation">(</span><span class="token keyword">int</span> v<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>sum <span class="token operator">=</span> v<span class="token punctuation">;</span> tar <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> lson <span class="token operator">=</span> rson <span class="token operator">=</span> <span class="token constant">NULL</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
    <span class="token keyword">void</span> <span class="token function">updata</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        sum <span class="token operator">=</span> <span class="token punctuation">(</span>lson <span class="token operator">-></span> sum <span class="token operator">+</span> rson <span class="token operator">-></span> sum <span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span><span class="token operator">*</span>null<span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">build</span><span class="token punctuation">(</span>Node <span class="token operator">*</span>o<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">,</span> <span class="token keyword">int</span> r<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>l <span class="token operator">==</span> r<span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        o <span class="token operator">-></span> sum <span class="token operator">=</span> NodeVal<span class="token punctuation">[</span>_rank<span class="token punctuation">[</span>l<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
        o <span class="token operator">-></span> lson <span class="token operator">=</span> null<span class="token punctuation">;</span>
        o <span class="token operator">-></span> rson <span class="token operator">=</span> null<span class="token punctuation">;</span>
        <span class="token keyword">return</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">int</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>l <span class="token operator">+</span> r<span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span>
    o <span class="token operator">-></span> lson <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">Node</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    o <span class="token operator">-></span> rson <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">Node</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">build</span><span class="token punctuation">(</span>o <span class="token operator">-></span> lson<span class="token punctuation">,</span> l<span class="token punctuation">,</span> mid<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">build</span><span class="token punctuation">(</span>o <span class="token operator">-></span> rson<span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> r<span class="token punctuation">)</span><span class="token punctuation">;</span>
    o <span class="token operator">-></span> <span class="token function">updata</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">void</span> <span class="token function">tar</span><span class="token punctuation">(</span>Node <span class="token operator">*</span>o<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">,</span><span class="token keyword">int</span> r<span class="token punctuation">,</span><span class="token keyword">int</span> v<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>o <span class="token operator">==</span> <span class="token constant">NULL</span><span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>
    o <span class="token operator">-></span> sum <span class="token operator">+=</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>r <span class="token operator">-</span> l <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token number">1LL</span> <span class="token operator">*</span> v<span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
    o <span class="token operator">-></span> sum <span class="token operator">%=</span> MOD<span class="token punctuation">;</span>
    o <span class="token operator">-></span> tar <span class="token operator">+=</span> v<span class="token punctuation">;</span>
    o <span class="token operator">-></span> tar <span class="token operator">%=</span> MOD<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">void</span> <span class="token function">push</span><span class="token punctuation">(</span>Node <span class="token operator">*</span>o<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">,</span> <span class="token keyword">int</span> r<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>l <span class="token operator">+</span> r<span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>o <span class="token operator">-></span> tar <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>
    <span class="token function">tar</span><span class="token punctuation">(</span>o <span class="token operator">-></span> lson<span class="token punctuation">,</span> l<span class="token punctuation">,</span> mid<span class="token punctuation">,</span> o <span class="token operator">-></span> tar<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">tar</span><span class="token punctuation">(</span>o <span class="token operator">-></span> rson<span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> r<span class="token punctuation">,</span> o <span class="token operator">-></span> tar <span class="token operator">%</span> MOD<span class="token punctuation">)</span><span class="token punctuation">;</span>
    o <span class="token operator">-></span> tar <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">query</span><span class="token punctuation">(</span>Node <span class="token operator">*</span>o<span class="token punctuation">,</span> <span class="token keyword">int</span> nowl<span class="token punctuation">,</span> <span class="token keyword">int</span> nowr<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">,</span> <span class="token keyword">int</span> r<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>l <span class="token operator">&lt;=</span> nowl <span class="token operator">&amp;&amp;</span> nowr <span class="token operator">&lt;=</span> r<span class="token punctuation">)</span>
        <span class="token keyword">return</span> o <span class="token operator">-></span> sum<span class="token punctuation">;</span>
    <span class="token function">push</span><span class="token punctuation">(</span>o<span class="token punctuation">,</span> nowl<span class="token punctuation">,</span> nowr<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>nowl <span class="token operator">+</span> nowr<span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>l <span class="token operator">&lt;=</span> mid<span class="token punctuation">)</span> ans <span class="token operator">=</span> <span class="token punctuation">(</span>ans <span class="token operator">+</span> <span class="token function">query</span><span class="token punctuation">(</span>o <span class="token operator">-></span> lson<span class="token punctuation">,</span> nowl<span class="token punctuation">,</span> mid<span class="token punctuation">,</span> l<span class="token punctuation">,</span> r<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>r <span class="token operator">></span> mid<span class="token punctuation">)</span>  ans <span class="token operator">=</span> <span class="token punctuation">(</span>ans <span class="token operator">+</span> <span class="token function">query</span><span class="token punctuation">(</span>o <span class="token operator">-></span> rson<span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> nowr<span class="token punctuation">,</span> l<span class="token punctuation">,</span>  r<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
    <span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">void</span> <span class="token function">change</span><span class="token punctuation">(</span>Node <span class="token operator">*</span>o<span class="token punctuation">,</span> <span class="token keyword">int</span> nowl<span class="token punctuation">,</span> <span class="token keyword">int</span> nowr<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">,</span> <span class="token keyword">int</span> r<span class="token punctuation">,</span> <span class="token keyword">int</span> v<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>l <span class="token operator">&lt;=</span> nowl <span class="token operator">&amp;&amp;</span> nowr <span class="token operator">&lt;=</span> r<span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        <span class="token function">tar</span><span class="token punctuation">(</span>o<span class="token punctuation">,</span> nowl<span class="token punctuation">,</span> nowr<span class="token punctuation">,</span> v<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> <span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">push</span><span class="token punctuation">(</span>o<span class="token punctuation">,</span> nowl<span class="token punctuation">,</span> nowr<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>nowl <span class="token operator">+</span> nowr<span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>l <span class="token operator">&lt;=</span> mid<span class="token punctuation">)</span> <span class="token function">change</span><span class="token punctuation">(</span>o <span class="token operator">-></span> lson<span class="token punctuation">,</span> nowl<span class="token punctuation">,</span> mid<span class="token punctuation">,</span> l<span class="token punctuation">,</span> r<span class="token punctuation">,</span> v<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>r <span class="token operator">></span> mid<span class="token punctuation">)</span>  <span class="token function">change</span><span class="token punctuation">(</span>o <span class="token operator">-></span> rson<span class="token punctuation">,</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> nowr<span class="token punctuation">,</span> l<span class="token punctuation">,</span> r<span class="token punctuation">,</span> v<span class="token punctuation">)</span><span class="token punctuation">;</span>
    o <span class="token operator">-></span> <span class="token function">updata</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">void</span> <span class="token function">AddOnPath</span><span class="token punctuation">(</span>Node <span class="token operator">*</span>root<span class="token punctuation">,</span> <span class="token keyword">int</span> L<span class="token punctuation">,</span> <span class="token keyword">int</span> A<span class="token punctuation">,</span> <span class="token keyword">int</span> B<span class="token punctuation">,</span> <span class="token keyword">int</span> Val<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>top<span class="token punctuation">[</span>A<span class="token punctuation">]</span> <span class="token operator">!=</span> top<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>depth<span class="token punctuation">[</span>top<span class="token punctuation">[</span>A<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">></span> depth<span class="token punctuation">[</span>top<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token function">swap</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> B<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">change</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> L<span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>top<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">,</span> Val<span class="token punctuation">)</span><span class="token punctuation">;</span>
        B <span class="token operator">=</span> fa<span class="token punctuation">[</span>top<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">change</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> L<span class="token punctuation">,</span> <span class="token function">min</span><span class="token punctuation">(</span>dfn<span class="token punctuation">[</span>A<span class="token punctuation">]</span><span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">max</span><span class="token punctuation">(</span>dfn<span class="token punctuation">[</span>A<span class="token punctuation">]</span><span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> Val<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">GetOnPath</span><span class="token punctuation">(</span>Node <span class="token operator">*</span>root<span class="token punctuation">,</span> <span class="token keyword">int</span> L<span class="token punctuation">,</span> <span class="token keyword">int</span> A<span class="token punctuation">,</span> <span class="token keyword">int</span> B<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>top<span class="token punctuation">[</span>A<span class="token punctuation">]</span> <span class="token operator">!=</span> top<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>depth<span class="token punctuation">[</span>top<span class="token punctuation">[</span>A<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">></span> depth<span class="token punctuation">[</span>top<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token function">swap</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> B<span class="token punctuation">)</span><span class="token punctuation">;</span>
        ans <span class="token operator">+=</span> <span class="token function">query</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> L<span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>top<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        ans <span class="token operator">%=</span> MOD<span class="token punctuation">;</span>
        B <span class="token operator">=</span> fa<span class="token punctuation">[</span>top<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    ans <span class="token operator">+=</span> <span class="token function">query</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> L<span class="token punctuation">,</span> <span class="token function">min</span><span class="token punctuation">(</span>dfn<span class="token punctuation">[</span>A<span class="token punctuation">]</span><span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">max</span><span class="token punctuation">(</span>dfn<span class="token punctuation">[</span>A<span class="token punctuation">]</span><span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>B<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    ans <span class="token operator">%=</span> MOD<span class="token punctuation">;</span>
    <span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">inline</span> <span class="token keyword">void</span> <span class="token function">AddOnSub</span><span class="token punctuation">(</span>Node <span class="token operator">*</span> root<span class="token punctuation">,</span> <span class="token keyword">int</span> L<span class="token punctuation">,</span> <span class="token keyword">int</span> now<span class="token punctuation">,</span> <span class="token keyword">int</span> V<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token function">change</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> L<span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">+</span> size<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> V<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token function">GetOnSub</span><span class="token punctuation">(</span>Node <span class="token operator">*</span>root<span class="token punctuation">,</span> <span class="token keyword">int</span> L<span class="token punctuation">,</span> <span class="token keyword">int</span> now<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">return</span> <span class="token function">query</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> L<span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>now<span class="token punctuation">]</span><span class="token punctuation">,</span> dfn<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">+</span> size<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> n <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> m <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> r <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> p <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>MOD <span class="token operator">=</span> p<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span>i <span class="token operator">++</span><span class="token punctuation">)</span>
        NodeVal<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> tmpx <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> tmpy <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">add</span><span class="token punctuation">(</span>tmpx<span class="token punctuation">,</span> tmpy<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">add</span><span class="token punctuation">(</span>tmpy<span class="token punctuation">,</span> tmpx<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">dfsinit</span><span class="token punctuation">(</span>r<span class="token punctuation">,</span> r<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">Dfs_Lct</span><span class="token punctuation">(</span>r<span class="token punctuation">,</span> r<span class="token punctuation">)</span><span class="token punctuation">;</span>
    Node <span class="token operator">*</span>root <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">Node</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    null <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">Node</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">build</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">register</span> <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i <span class="token operator">&lt;=</span> m<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> opt <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> A<span class="token punctuation">,</span> B<span class="token punctuation">,</span> Val<span class="token punctuation">,</span> R<span class="token punctuation">;</span>
        <span class="token keyword">switch</span><span class="token punctuation">(</span>opt<span class="token punctuation">)</span>
        <span class="token punctuation">&#123;</span>
            <span class="token keyword">case</span> <span class="token number">1</span> <span class="token operator">:</span>
                A <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> B <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> Val <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">%</span>MOD<span class="token punctuation">;</span>
                <span class="token function">AddOnPath</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> n<span class="token punctuation">,</span> A<span class="token punctuation">,</span> B<span class="token punctuation">,</span> Val<span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token keyword">case</span> <span class="token number">2</span> <span class="token operator">:</span>
                A <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> B <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d\n"</span><span class="token punctuation">,</span> <span class="token function">GetOnPath</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> n<span class="token punctuation">,</span> A<span class="token punctuation">,</span> B<span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token keyword">case</span> <span class="token number">3</span> <span class="token operator">:</span>
                R <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> Val <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
                <span class="token function">AddOnSub</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> n<span class="token punctuation">,</span> R<span class="token punctuation">,</span> Val<span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token keyword">case</span> <span class="token number">4</span> <span class="token operator">:</span>
                R <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d\n"</span><span class="token punctuation">,</span> <span class="token function">GetOnSub</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> n<span class="token punctuation">,</span> R<span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2019/【luogu-3037】【USACO11DEC】简化的农场Simplifying-the-Farm/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/2019/%E3%80%90luogu-3037%E3%80%91%E3%80%90USACO11DEC%E3%80%91%E7%AE%80%E5%8C%96%E7%9A%84%E5%86%9C%E5%9C%BASimplifying-the-Farm/" class="post-title-link" itemprop="url">【luogu-P3037】【USACO11DEC】简化的农场Simplifying the Farm</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2019-08-04 09:40:21" itemprop="dateCreated datePublished" datetime="2019-08-04T09:40:21+08:00">2019-08-04</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2020-04-27 11:33:31" itemprop="dateModified" datetime="2020-04-27T11:33:31+08:00">2020-04-27</time>
      </span>

  
    <span id="2019/【luogu-3037】【USACO11DEC】简化的农场Simplifying-the-Farm/" class="post-meta-item leancloud_visitors" data-flag-title="【luogu-P3037】【USACO11DEC】简化的农场Simplifying the Farm" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2019/【luogu-3037】【USACO11DEC】简化的农场Simplifying-the-Farm/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2019/【luogu-3037】【USACO11DEC】简化的农场Simplifying-the-Farm/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>2.6k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>2 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="思路"><a href="#思路" class="headerlink" title="思路"></a>思路</h1><p>如果没有边权相同的边，那么其实时不存在多种最小生成树的方案的。</p>
<p>题目中同一边权的个数不超过三个</p>
<p>按照<code>Kruskal</code>的建树流程进行模拟。</p>
<p>边权排完序后，边权相同的会聚到一起，然后在从小到大枚举的时候分类讨论即可。</p>
          <!--noindex-->
            <div class="post-button">
              <a class="btn" href="/2019/【luogu-3037】【USACO11DEC】简化的农场Simplifying-the-Farm/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          <!--/noindex-->
        
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
  
  
  


  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/page/5/"><i class="fa fa-angle-left" aria-label="上一页"></i></a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/5/">5</a><span class="page-number current">6</span><a class="page-number" href="/page/7/">7</a><span class="space">&hellip;</span><a class="page-number" href="/page/11/">11</a><a class="extend next" rel="next" href="/page/7/"><i class="fa fa-angle-right" aria-label="下一页"></i></a>
  </nav>



      

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      const activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      const commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

    </div>
  </main>

  <footer class="footer">
    <div class="footer-inner">
      

      

<div class="copyright">
  
  &copy; 2018 – 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">舒雨墨</span>
</div>
<div class="wordcount">
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-chart-line"></i>
    </span>
    <span title="站点总字数">319k</span>
  </span>
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
    <span title="站点阅读时长">4:50</span>
  </span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/mist/" class="theme-link" rel="noopener" target="_blank">NexT.Mist</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <script src="//cdn.jsdelivr.net/npm/animejs@3.2.0/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/@next-theme/pjax@0.4.0/pjax.min.js"></script>
<script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/schemes/muse.js"></script><script src="/js/next-boot.js"></script>
  <script>
var pjax = new Pjax({
  selectors: [
    'head title',
    '.page-configurations',
    '.main-inner',
    '.post-toc-wrap',
    '.languages',
    '.pjax'
  ],
  analytics: false,
  cacheBust: false,
  scrollRestoration: false,
  scrollTo: !CONFIG.bookmark.enable
});

document.addEventListener('pjax:success', () => {
  pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
  NexT.boot.refresh();
  // Define Motion Sequence & Bootstrap Motion.
  if (CONFIG.motion.enable) {
    NexT.motion.integrator
      .init()
      .add(NexT.motion.middleWares.subMenu)
      .add(NexT.motion.middleWares.postList)
      .bootstrap();
  }
  const hasTOC = document.querySelector('.post-toc');
  document.querySelector('.sidebar-inner').classList.toggle('sidebar-nav-active', hasTOC);
  document.querySelector(hasTOC ? '.sidebar-nav-toc' : '.sidebar-nav-overview').click();
  NexT.utils.updateSidebarPosition();
});
</script>


  
  <script data-pjax>
    (function(){
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      bp.src = (curProtocol === 'https') ? 'https://zz.bdstatic.com/linksubmit/push.js' : 'http://push.zhanzhang.baidu.com/push.js';
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
    })();
  </script>




  <script src="/js/local-search.js"></script>












  






<script data-pjax>
  (function() {
    function leancloudSelector(url) {
      return document.getElementById(url).querySelector('.leancloud-visitors-count');
    }

    function addCount(Counter) {
      const visitors = document.querySelector('.leancloud_visitors');
      const url = decodeURI(visitors.id);
      const title = visitors.dataset.flagTitle;

      Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({ url })))
        .then(response => response.json())
        .then(({ results }) => {
          if (results.length > 0) {
            const counter = results[0];
            leancloudSelector(url).innerText = counter.time + 1;
            Counter('put', '/classes/Counter/' + counter.objectId, { time: { '__op': 'Increment', 'amount': 1 } })
              .catch(error => {
                console.error('Failed to save visitor count', error);
              });
          } else {
              Counter('post', '/classes/Counter', { title, url, time: 1 })
                .then(response => response.json())
                .then(() => {
                  leancloudSelector(url).innerText = 1;
                })
                .catch(error => {
                  console.error('Failed to create', error);
                });
          }
        })
        .catch(error => {
          console.error('LeanCloud Counter Error', error);
        });
    }

    function showTime(Counter) {
      const visitors = document.querySelectorAll('.leancloud_visitors');
      const entries = [...visitors].map(element => {
        return decodeURI(element.id);
      });
      Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({ url: { '$in': entries } })))
        .then(response => response.json())
        .then(({ results }) => {
          for (let url of entries) {
            const target = results.find(item => item.url === url);
            leancloudSelector(url).innerText = target ? target.time : 0;
          }
        })
        .catch(error => {
          console.error('LeanCloud Counter Error', error);
        });
    }

    const { app_id, app_key, server_url } = {"enable":true,"app_id":"Tw3wqSuCQwL4zK5pGCd6BkKa-gzGzoHsz","app_key":"lwlhdaYvNPPDLhBEGeUegbH6","server_url":null,"security":false};
    function fetchData(api_server) {
      const Counter = (method, url, data) => {
        return fetch(`${api_server}/1.1${url}`, {
          method,
          headers: {
            'X-LC-Id'     : app_id,
            'X-LC-Key'    : app_key,
            'Content-Type': 'application/json',
          },
          body: JSON.stringify(data)
        });
      };
      if (CONFIG.page.isPost) {
        if (location.hostname == '127.0.0.1' || location.hostname == 'localhost') ;
        else addCount(Counter);
      }
      if (document.querySelectorAll('.post-title-link').length >= 1 || document.querySelectorAll('.post-title').length >= 1) {
        showTime(Counter);
      }
    }

    const api_server = app_id.slice(-9) !== '-MdYXbMMI' ? server_url : `https://${app_id.slice(0, 8).toLowerCase()}.api.lncldglobal.com`;

    if (api_server) {
      fetchData(api_server);
    } else {
      fetch('https://app-router.leancloud.cn/2/route?appId=' + app_id)
        .then(response => response.json())
        .then(({ api_server }) => {
          fetchData('https://' + api_server);
        });
    }
  })();
</script>


    <div class="pjax">
  

  
      <script>
  if (typeof MathJax === 'undefined') {
    window.MathJax = {
      tex: {
        inlineMath: {'[+]': [['$', '$']]},
        tags: 'ams'
      },
      options: {
        renderActions: {
          findScript: [10, doc => {
            document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
              const display = !!node.type.match(/; *mode=display/);
              const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
              const text = document.createTextNode('');
              node.parentNode.replaceChild(text, node);
              math.start = {node: text, delim: '', n: 0};
              math.end = {node: text, delim: '', n: 0};
              doc.math.push(math);
            });
          }, '', false],
          insertedScript: [200, () => {
            document.querySelectorAll('mjx-container').forEach(node => {
              const target = node.parentNode;
              if (target.nodeName.toLowerCase() === 'li') {
                target.parentNode.classList.add('has-jax');
              }
            });
          }, '', false]
        }
      }
    };
    const script = document.createElement('script');
    script.src = '//cdn.jsdelivr.net/npm/mathjax@3.1.0/es5/tex-mml-chtml.js';
    script.defer = true;
    document.head.appendChild(script);
  } else {
    MathJax.startup.document.state(0);
    MathJax.typesetClear();
    MathJax.texReset();
    MathJax.typeset();
  }
</script>

    

  
<script>
NexT.utils.loadComments('#valine-comments', () => {
  NexT.utils.getScript('//cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js', () => {
    new Valine(Object.assign({
      el  : '#valine-comments',
      path: "page/6/",
    }, {"enable":true,"appId":"Tw3wqSuCQwL4zK5pGCd6BkKa-gzGzoHsz","appKey":"lwlhdaYvNPPDLhBEGeUegbH6","placeholder":"Just go go","avatar":"mm","meta":["nick","mail","link"],"pageSize":10,"lang":"zh-cn","visitor":false,"comment_count":true,"recordIP":true,"serverURLs":null,"enableQQ":true,"requiredFields":[]}
    ));
  }, window.Valine);
});
</script>

    </div>
</body>
</html>
